// https://www.lintcode.com/problem/maximum-binary-tree/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    /**
     * @param nums: an array
     * @return: the maximum tree
     */
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        // Write your code here
        return _constructMaximumBinaryTree(nums, 0, nums.length);
    }
    
    protected TreeNode _constructMaximumBinaryTree(int[] nums, int start, int end) {
        if (start >= end) {
            return null;
        } else if (start == (end - 1)) {
            return new TreeNode(nums[start]);
        } else {
            int max = nums[start], cp = start;
            for (int i = start + 1; i < end; ++i) {
                if (nums[i] > max) {
                    max = nums[i];
                    cp = i;
                }
            }
            TreeNode node = new TreeNode(max);
            node.left = _constructMaximumBinaryTree(nums, start, cp);
            node.right = _constructMaximumBinaryTree(nums, cp + 1, end);
            return node;
        }
    }
}